#the main controller is the class that controls the entire website (in its current form)
#the actions defined below are the various pages and actions that can be performed on the
#site
class MainController < ApplicationController
	attr_accessor :tree

	#the view page is a default "wrapper" page that contains the
	#home, demo, about and contact pages. This page is the default
	#route of the application
	def view
	end

	#Step 0
	#the "home" page that contains the actual program that we are creating
	def home
		@list_of_tables  = TABLES.find(:all, :conditions => ["TABLE_SCHEMA = 'company'"])
		@list_of_cols    = COLUMNS.find(:all, :conditions => ["TABLE_SCHEMA = 'company'"])
		@list_of_indexes = STATISTICS.find(:all, :conditions => ["TABLE_SCHEMA = 'company'"])
	end

	#the "demo" page displays a demonstration of our project
	def demo
	end
	
	def test
	end

	#the "about" page display information about the project and links to more information
	def about
	end

	#the "contact" page displays information on how to contact the authors
	def contact
	end

	#Step 1
	#the translate action translates a given SQL query into the PJS Form for our project
	#PJS => Project, Join, Scan
	def translate
		#check to see if the query is empty
		#if so, break from the translation process
		if params[:query].eql?("")
			render_text "No query given. Please enter a query!"
			return
		end
		
		#parse the query into a manageable form with
		#the projections, predicates and joins all separated
		#into an associative array of the form
		#{:projections => ..., :join_preds => ..., :select_preds => ..., :tables => ...}
		parsed_statement = parse(params[:query])
		
		#if the parser returns an error, report the error to the UI
		if parsed_statement.eql?("error")
			render_text "Oops, an invalid query was specified. Please refine your query and try again!"
			return
		end
		
		#Description of the algorithm
		#Why the algorithm produces the result
		#Create the forms and tabs necessary for this step
		algorithm = "<p>In this step, the query optimizer takes the query and processes it into a more machine-friendly version.</p>
					  <ol class='code'>
						<li>Parse the query into projections, select predicates, join predicates, and tables</li>
						<li>Store the parsed statement into a binary tree</li>
					  </ol>"
					  
		why =  "<p>The list structure you see is the external representation of the internal binary tree used to store the parsed query. Currently, all joins are still represented as Cross Products and all of the joins are binary. Here is the way the list structure can be interpreted:</p>
				<ul>
					<li>(PROJECT (projection_list) (relation))</li>
					<li>(SELECT (select_predicates) (relation))</li>
					<li>(CROSS (join_predicates) (outer_relation) (inner_relation))</li>
					<li>(TABLE (relation))</li>
				</ul>"
		
		tabs = ["alg","why"]
		tabs_t = ["Algorithm","Explain"]
		tabs_c = []
		tabs_c << algorithm
		tabs_c << why		
		#render_text generate_form(2.to_s, tabs, tabs_t, tabs_c, createTree( parsed_statement ).to_s, "breakselects", "broken_selects", "step_three", params[:query])
		render_text generate_form(2.to_s, tabs, tabs_t, tabs_c, createTree( parsed_statement ).to_svg, "breakselects", "broken_selects", "step_three", params[:query])
		return
	end

	#Step 2
	#Removes the selects from the top level and reinserts them
	#one by one, placing them in the correct spot
	def breakselects
		#Parses the query into an array of objects
		#Creates the tree form of the query that we'll use throughout
		#Removes the predicates from the top of the tree
		parsed_statement = parse(params[:query])
		tree = createTree( parsed_statement )
		tree.removeSelects

		#Puts the select predicates back in the tree, one by one
		for x in parsed_statement[:select_preds]
			tree.insertSelectPredicate x
		end
		#Puts the join predicates back in the tree, one by one
		for x in parsed_statement[:join_preds]
			tree.insertJoinPredicate x
		end

		##RMagick is currently *not* working
		##load "CreateImage.rb"

		#Description of the algorithm
		#Why the algorithm produces the result
		#Create the forms and tabs necessary for this step
		algorithm = 
						"<p>In this step, the selects are pushed down the tree.</p>
						<ol class='code'>
							<li>Remove all select statments</li>
							<li>Insert the select predicates one by one</li>
							<li>Insert the join predicates one by one</li>
						</ol>"
		why = "<p>This is done so that the relations are as small as possible before
						joining them, resulting in increased efficiency in nearly all cases.
						For more information, please refer to the referenced papers in the about section.</p>"
						
		tabs = ["alg","why"]
		tabs_t = ["Algorithm","Explain"]
		tabs_c = []
		tabs_c << algorithm
		tabs_c << why
		render_text generate_form(3.to_s, tabs, tabs_t, tabs_c, tree.to_s, "order_joins", "join_ordered", "step_four", params[:query])
		return
	end

	#Step 3
	#Orders the joins so that the outer joins are the most selective
	def order_joins
		#Parses the query into an array of objects
		#Creates the tree form of the query that we'll use throughout
		#Removes the predicates from the top of the tree
		parsed_statement = parse(params[:query])
		tree = createTree( parsed_statement )
		tree.removeSelects

		#Puts the select predicates back in the tree, one by one
		for x in parsed_statement[:select_preds]
			tree.insertSelectPredicate x
		end

		#If there is only one table, nothing more needs to be done
		if parsed_statement[:tables].length == 1
			#Puts the join predicates back in the tree, one by one
			for x in parsed_statement[:join_preds]
				tree.insertJoinPredicate x
			end

			#Description of the algorithm
			#Why the algorithm produces the result
			#Create the forms and tabs necessary for this step
			algorithm = "<p>In this step, the tables (and their associated selects) are 
										ordered so that the outer join is always smaller than its inner counterpart.</p>
						<ol class='code'>
							<li>Generate all possible join orders</li>
							<li>Check all join orders to find the smallest</li>
							<li>Recreate the tree using the new join order</li>
						</ol>"
			why = "The algorithm does this step in order to reduce cost. Again, this part of the algorithm is all
							guesswork that is based on generalizations and limited data available. So, while this may not
							always produce the best order in some cases, it will always be a good result--even if not perfect. Close counts."
			tabs = ["alg","why"]
			tabs_t = ["Algorithm","Explain"]
			tabs_c = []
			tabs_c << algorithm
			tabs_c << why
			render_text generate_form(4.to_s, tabs, tabs_t, tabs_c, tree.to_s, "merge_joins", "merged_joins", "step_five", params[:query])
			return
		end

		#Generates all possible join orders
		# ---
		#Initializes the smallest as the first of the array
		ordered_joins = generate_joins( tree.grabTables )
		preds = parsed_statement[:join_preds]
		smallest = Array.new ordered_joins[0]
		smallest_value = get_size( smallest, preds, [] )
		joinOrders = "<p>These are the possible join orders. The highlighted order was determined to be the optimal join order.</p><ul>"

		#Checks all join orders to find the smallest
		for x in ordered_joins
			t = Array.new(x)
			s = Array.new(smallest)
			z = get_size( t, preds, [] )
			#add the join order to the output file
			joinOrders += "<li>" + x.to_s + "</li>"
			#if the size of the join order t is smaller than smallest
			#then set the smallest to join order t (x)
			if z < smallest_value
				smallest = x
				smallest_value = z
			end
		end

		#add the smallest as the "correct result"
		joinOrders += "<li class='correct_join_order'><span>" + smallest.to_s + "</span></li></ul>"


		#Create a new tree based on the new order
		newTree = createTreePushed( {:projections => parsed_statement[:projections], 
																 :join_preds  => parsed_statement[:join_preds],
																 :tables => smallest.reverse} )
		#Again, remove the selects
		#Insert the join predicates
		newTree.removeSelects
		for x in parsed_statement[:join_preds]
			newTree.insertJoinPredicate x
		end

		#Description of the algorithm
		#Why the algorithm produces the result
		#Create the forms and tabs necessary for this step
		algorithm = "<p>In this step, the tables (and their associated selects) are 
									ordered so that the outer join is always smaller than its inner counterpart.</p>
					<ol class='code'>
						<li>Generate all possible join orders</li>
						<li>Check all join orders to find the smallest</li>
						<li>Recreate the tree using the new join order</li>
					</ol>"
		why = "The algorithm does this step in order to reduce cost. Again, this part of the algorithm is all
						guesswork that is based on generalizations and limited data available. So, while this may not
						always produce the best order in some cases, it will always be a good result--even if not perfect. Close counts."
		tabs = ["join","alg","why"]
		tabs_t = ["Join Orders","Algorithm","Explain"]
		tabs_c = []
		tabs_c << joinOrders
		tabs_c << algorithm
		tabs_c << why
		render_text generate_form(4.to_s, tabs, tabs_t, tabs_c, newTree.to_s, "merge_joins", "merged_joins", "step_five", params[:query])
		return
	end

	#Step 4
	#Merges the join predicates down into cross products, making them joins
	def merge_joins
		#Parses the query into an array of objects
		#Creates the tree form of the query that we'll use throughout
		#Removes the predicates from the top of the tree
		parsed_statement = parse(params[:query])
		tree = createTree( parsed_statement )
		tree.removeSelects

		#Puts the select predicates back in the tree, one by one
		for x in parsed_statement[:select_preds]
			tree.insertSelectPredicate x
		end

		#If there is only one table, nothing more needs to be done
		if parsed_statement[:tables].length == 1
			#Puts the join predicates back in the tree, one by one
			for x in parsed_statement[:join_preds]
				tree.insertJoinPredicate x
			end

			#Description of the algorithm
			#Why the algorithm produces the result
			#Create the forms and tabs necessary for this step
			algorithm = "<p>In this step, the join predicates and the cross products are merged to create joins.</p>
						<ol class='code'>
							<li>Traverse the tree, find all selects</li>
							<li>For each select</li>
							<li>if chosen select has a child of type CROSS</li>
							<li>then collapse</li>
							<li>else do nothing</li>
						</ol>"
			why = "<p>Merging these is a matter of symantics. The algorithm does this so that the cost-based optimizer can more readily determine whether
							the join is a cross product or not.</p>
						<p>Note: (CROSS (predicate) (R1) (R2)) with a predicate present is NOT a CROSS product join but, instead, some other type of join yet to be
						determined. The cost-based optimizer will determine the type.</p>"
			tabs = ["alg","why"]
			tabs_t = ["Algorithm","Explain"]
			tabs_c = []
			tabs_c << algorithm
			tabs_c << why
			render_text generate_form(5.to_s, tabs, tabs_t, tabs_c, tree.to_s, "push_projects", "pushed_projects", "step_six", params[:query])
			return
		end

		#Generates all possible join orders
		# ---
		#Initializes the smallest as the first of the array
		ordered_joins = generate_joins( tree.grabTables )
		preds = parsed_statement[:join_preds]
		smallest = Array.new ordered_joins[0]
		smallest_value = get_size( smallest, preds, [] )

		#Checks all join orders to find the smallest
		for x in ordered_joins
			t = Array.new(x)
			s = Array.new(smallest)
			z = get_size( t, preds, [] )
			#if the size of the join order t is smaller than smallest
			#then set the smallest to join order t (x)
			if z < smallest_value
				smallest = x
				smallest_value = z
			end
		end
		
		#Create a new tree based on the new order
		newTree = createTreePushed( {:projections => parsed_statement[:projections], 
																 :join_preds  => parsed_statement[:join_preds],
																 :tables => smallest.reverse} )
		#Again, remove the selects
		#Insert the join predicates
		newTree.removeSelects
		for x in parsed_statement[:join_preds]
			newTree.insertJoinPredicate x
		end

		#Merge the joins
		newTree.mergeJoins

		#Description of the algorithm
		#Why the algorithm produces the result
		#Create the forms and tabs necessary for this step
		algorithm = "<p>In this step, the join predicates and the cross products are merged to create joins.</p>
					<ol class='code'>
						<li>Traverse the tree, find all selects</li>
						<li>For each select</li>
						<li>if chosen select has a child of type CROSS</li>
						<li>then collapse</li>
						<li>else do nothing</li>
					</ol>"
		why = "<p>Merging these is a matter of symantics. The algorithm does this so that the cost-based optimizer can more readily determine whether
						the join is a cross product or not.</p>
					<p>Note: (CROSS (predicate) (R1) (R2)) with a predicate present is NOT a CROSS product join but, instead, some other type of join yet to be
					determined. The cost-based optimizer will determine the type.</p>"
		tabs = ["alg","why"]
		tabs_t = ["Algorithm","Explain"]
		tabs_c = []
		tabs_c << algorithm
		tabs_c << why
		render_text generate_form(5.to_s, tabs, tabs_t, tabs_c, newTree.to_s, "push_projects", "pushed_projects", "step_six", params[:query])
		return
	end

	# Step 5
	# Pushes the projects ahead of joins to make the tables even more selective, improving performace
	def push_projects
		#Parses the query into an array of objects
		#Creates the tree form of the query that we'll use throughout
		#Removes the predicates from the top of the tree
		parsed_statement = parse(params[:query])
		tree = createTree( parsed_statement )
		tree.removeSelects
		
		#Puts the select predicates back in the tree, one by one
		for x in parsed_statement[:select_preds]
			tree.insertSelectPredicate x
		end

		#If there is only one table, nothing more needs to be done
		if parsed_statement[:tables].length == 1
			#Puts the join predicates back in the tree, one by one
			for x in parsed_statement[:join_preds]
				tree.insertJoinPredicate x
			end

			#Description of the algorithm
			#Why the algorithm produces the result
			#Create the forms and tabs necessary for this step
			algorithm = "<p>In this step, the projections are pushed as far along the tree as they can go.</p>
						<ol class='code'>
							<li>Read the selects</li>
							<li>Insert the selects one by one</li>
							<li>As you pass a join or select, add in additional projects</li>
						</ol>"
			why = "<p>Pushing the projections will further eliminate \"useless\" information. This will increase the efficiency
			the join algorithms</p>"			
			tabs = ["alg","why"]
			tabs_t = ["Algorithm","Explain"]
			tabs_c = []
			tabs_c << algorithm
			tabs_c << why
			render_text generate_form(6.to_s, tabs, tabs_t, tabs_c, tree.to_s, "table_scan", "scaned_tables", "step_seven", params[:query])
			return
		end
		
		#Generates all possible join orders
		# ---
		#Initializes the smallest as the first of the array
		ordered_joins = generate_joins( tree.grabTables )
		preds = parsed_statement[:join_preds]
		smallest = Array.new ordered_joins[0]
		smallest_value = get_size( smallest, preds, [] )

		#Checks all join orders to find the smallest
		for x in ordered_joins
			t = Array.new(x)
			s = Array.new(smallest)
			z = get_size( t, preds, [] )
			#if the size of the join order t is smaller than smallest
			#then set the smallest to join order t (x)
			if z < smallest_value
				smallest = x
				smallest_value = z
			end
		end

		#Create a new tree based on the new order
		newTree = createTreePushed( {:projections => parsed_statement[:projections], 
																 :join_preds  => parsed_statement[:join_preds],
																 :tables => smallest.reverse} )
		
		#Again, remove the selects
		#Insert the join predicates
		newTree.removeSelects
		for x in parsed_statement[:join_preds]
			newTree.insertJoinPredicate x
		end

		#Merge all of the join predicates into the cross products
		#to form joins
		newTree.mergeJoins

		#Push all of the selects
		for x in parsed_statement[:projections]
			newTree.insertProject x
		end
		
		#Description of the algorithm
		#Why the algorithm produces the result
		#Create the forms and tabs necessary for this step
		algorithm = "<p>In this step, the projections are pushed as far along the tree as they can go.</p>
					<ol class='code'>
						<li>Read the selects</li>
						<li>Insert the selects one by one</li>
						<li>As you pass a join or select, add in additional projects</li>
					</ol>"
		why = "<p>Pushing the projections will further eliminate \"useless\" information. This will increase the efficiency
		the join algorithms</p>"			
		tabs = ["alg","why"]
		tabs_t = ["Algorithm","Explain"]
		tabs_c = []
		tabs_c << algorithm
		tabs_c << why
		render_text generate_form(6.to_s, tabs, tabs_t, tabs_c, newTree.to_s, "table_scan", "scaned_tables", "step_seven", params[:query])
		return
	end
	
	#Step 6
	#Find what type of lookups needed on the tables
	def table_scan
		#Parses the query into an array of objects
		#Creates the tree form of the query that we'll use throughout
		#Removes the predicates from the top of the tree
		parsed_statement = parse(params[:query])
		tree = createTree( parsed_statement )
		tree.removeSelects

		#Puts the select predicates back in the tree, one by one
		for x in parsed_statement[:select_preds]
			tree.insertSelectPredicate x
		end

		#If there is only one table, nothing more needs to be done
		if parsed_statement[:tables].length == 1
			#Puts the join predicates back in the tree, one by one
			for x in parsed_statement[:join_preds]
				tree.insertJoinPredicate x
			end

			algorithm = "<p>In this step, the tables are parsed to check for the type of scans that they need.</p>
						<ol class='code'>
							<li>Scan for tables</li>
							<li>If the table is preceded by a select</li>
							<li>find the desired scan for the select</li>
							<li>for all tables, do a filescan</li>
						</ol>"
			why = "<p>This is the beginning of finishing the query evaluation plan that the executor will follow</p>"
			tabs = ["alg","why"]
			tabs_t = ["Algorithm","Explain"]
			tabs_c = []
			tabs_c << algorithm
			tabs_c << why
			render_text generate_form(7.to_s, tabs, tabs_t, tabs_c, tree.to_s, "join_scan", "scaned_joins", "step_eight", params[:query])
		end

		#Generates all possible join orders
		# ---
		#Initializes the smallest as the first of the array
		ordered_joins = generate_joins( tree.grabTables )
		preds = parsed_statement[:join_preds]
		smallest = Array.new ordered_joins[0]
		smallest_value = get_size( smallest, preds, [] )

		#Checks all join orders to find the smallest
		for x in ordered_joins
			t = Array.new(x)
			s = Array.new(smallest)
			z = get_size( t, preds, [] )
			#if the size of the join order t is smaller than smallest
			#then set the smallest to join order t (x)
			if z < smallest_value
				smallest = x
				smallest_value = z
			end
		end

		#Create a new tree based on the new order
		newTree = createTreePushed( {:projections => parsed_statement[:projections], 
																 :join_preds  => parsed_statement[:join_preds],
																 :tables => smallest.reverse} )

		#Again, remove the selects
		#Insert the join predicates
		newTree.removeSelects
		for x in parsed_statement[:join_preds]
			newTree.insertJoinPredicate x
		end

		#Merge all of the join predicates into the cross products
		#to form joins
		newTree.mergeJoins

		#Push all of the selects
		for x in parsed_statement[:projections]
			newTree.insertProject x
		end

		#Scan the tree and find how to scan the tables
		newTree.tableScan

		#Description of the algorithm
		#Why the algorithm produces the result
		#Create the forms and tabs necessary for this step
			algorithm = "<p>In this step, the tables are parsed to check for the type of scans that they need.</p>
						<ol class='code'>
							<li>Scan for tables</li>
							<li>If the table is preceded by a select</li>
							<li>find the desired scan for the select</li>
							<li>for all tables, do a filescan</li>
						</ol>"
			why = "<p>This is the beginning of finishing the query evaluation plan that the executor will follow</p>"
		tabs = ["alg","why"]
		tabs_t = ["Algorithm","Explain"]
		tabs_c = []
		tabs_c << algorithm
		tabs_c << why
		render_text generate_form(7.to_s, tabs, tabs_t, tabs_c, newTree.to_s, "join_scan", "scaned_joins", "step_eight", params[:query])
		return
	end

	#Step 7
	#Find what type of joins are needed
	def join_scan
		#Parses the query into an array of objects
		#Creates the tree form of the query that we'll use throughout
		#Removes the predicates from the top of the tree
		parsed_statement = parse(params[:query])
		tree = createTree( parsed_statement )
		tree.removeSelects

		#Puts the select predicates back in the tree, one by one
		for x in parsed_statement[:select_preds]
			tree.insertSelectPredicate x
		end

		#If there is only one table, nothing more needs to be done
		if parsed_statement[:tables].length == 1
			#Generates all possible join orders
			# ---
			#Initializes the smallest as the first of the array
			ordered_joins = generate_joins( tree.grabTables )
			preds = parsed_statement[:join_preds]
			smallest = Array.new ordered_joins[0]
			smallest_value = get_size( smallest, preds, [] )

			#Checks all join orders to find the smallest
			for x in ordered_joins
				t = Array.new(x)
				s = Array.new(smallest)
				z = get_size( t, preds, [] )
				#if the size of the join order t is smaller than smallest
				#then set the smallest to join order t (x)
				if z < smallest_value
					smallest = x
					smallest_value = z
				end
			end

			#Create a new tree based on the new order
			newTree = createTreePushed( {:projections => parsed_statement[:projections], 
																	 :join_preds  => parsed_statement[:join_preds],
																	 :tables => smallest.reverse} )

			#Again, remove the selects
			#Insert the join predicates
			newTree.removeSelects
			for x in parsed_statement[:join_preds]
				newTree.insertJoinPredicate x
			end

			#Merge all of the join predicates into the cross products
			#to form joins
			newTree.mergeJoins

			#Push all of the selects
			for x in parsed_statement[:projections]
				newTree.insertProject x
			end

			#Scan the tree and find how to scan the tables
			newTree.tableScan

			#Scan the tree and find how to join
			newTree.joinScan

			info = "<div class='tab_content'>
						<ul class='step_tabs'>
							<li title='info_8' onclick='tabs(this);'>The Numbers</li>
							<li title='alg_8' onclick='tabs(this);'>Algorithm</li>
							<li title='why_8' onclick='tabs(this);'>Explain</li>
						</ul>
						<div id='info_8'>"

			sql_tables = TABLES.find(:all, :conditions => ["TABLE_SCHEMA = 'company'"])
			info += "<table><tr><td style='padding-right: 20px'>Table Name</td><td style='padding-right: 10px'>Number of Rows</td><td>Avg. Data per Row</td></tr>"
			for x in sql_tables
				info += "<tr>" + "<td>" + x.TABLE_NAME.to_s + "</td><td>" + x.TABLE_ROWS.to_s + "</td><td>" + x.AVG_ROW_LENGTH.to_s + "</td></tr>"
			end
			info += "</table>"
			info +=	"</div>
						<div id='alg_8'>
							<p>Evaluate the joins and determine the type of join that needs to be processed.</p>
							<ol class='code'>
								<li>Scan the tree for each join</li>
								<li>Evaluate the join</li>
								<li>Determine, based on the previous evaluation, which join is best</li>
							</ol>
						</div>
						<div id='why_8'>
							<p>The purpose of this evaluation of the joins is to enable the query processor
							 to perform the necessary operations that will give the user their desired query.
							 After this step, the QEP is ready to be run through the query evaluator* and 
							 give the user their desired data.</p>
							<p>* ==> There may be some small parsing of the tree but not actual evaluation will
							be needed after this step.</p>
						</div>
					</div>"

			#Send the tree
			render_text info + newTree.to_s
		end

		#Generates all possible join orders
		# ---
		#Initializes the smallest as the first of the array
		ordered_joins = generate_joins( tree.grabTables )
		preds = parsed_statement[:join_preds]
		smallest = Array.new ordered_joins[0]
		smallest_value = get_size( smallest, preds, [] )

		#Checks all join orders to find the smallest
		for x in ordered_joins
			t = Array.new(x)
			s = Array.new(smallest)
			z = get_size( t, preds, [] )
			#if the size of the join order t is smaller than smallest
			#then set the smallest to join order t (x)
			if z < smallest_value
				smallest = x
				smallest_value = z
			end
		end

		#Create a new tree based on the new order
		newTree = createTreePushed( {:projections => parsed_statement[:projections], 
																 :join_preds  => parsed_statement[:join_preds],
																 :tables => smallest.reverse} )

		#Again, remove the selects
		#Insert the join predicates
		newTree.removeSelects
		for x in parsed_statement[:join_preds]
			newTree.insertJoinPredicate x
		end

		#Merge all of the join predicates into the cross products
		#to form joins
		newTree.mergeJoins

		#Push all of the selects
		for x in parsed_statement[:projections]
			newTree.insertProject x
		end

		#Scan the tree and find how to scan the tables
		newTree.tableScan

		#Scan the tree and find how to join
		newTree.joinScan

		info = "<div class='tab_content'>
					<ul class='step_tabs'>
						<li title='info_8' onclick='tabs(this);'>The Numbers</li>
						<li title='alg_8' onclick='tabs(this);'>Algorithm</li>
						<li title='why_8' onclick='tabs(this);'>Explain</li>
					</ul>
					<div id='info_8'>"
		
		sql_tables = TABLES.find(:all, :conditions => ["TABLE_SCHEMA = 'company'"])
		info += "<table><tr><td style='padding-right: 20px'>Table Name</td><td style='padding-right: 10px'>Number of Rows</td><td>Avg. Data per Row</td></tr>"
		for x in sql_tables
			info += "<tr>" + "<td>" + x.TABLE_NAME.to_s + "</td><td>" + x.TABLE_ROWS.to_s + "</td><td>" + x.AVG_ROW_LENGTH.to_s + "</td></tr>"
		end
		info += "</table>"
		info +=	"</div>
					<div id='alg_8'>
						<p>Evaluate the joins and determine the type of join that needs to be processed.</p>
						<ol class='code'>
							<li>Scan the tree for each join</li>
							<li>Evaluate the join</li>
							<li>Determine, based on the previous evaluation, which join is best</li>
						</ol>
					</div>
					<div id='why_8'>
						<p>The purpose of this evaluation of the joins is to enable the query processor
						 to perform the necessary operations that will give the user their desired query.
						 After this step, the QEP is ready to be run through the query evaluator* and 
						 give the user their desired data.</p>
						<p>* ==> There may be some small parsing of the tree but not actual evaluation will
						be needed after this step.</p>
					</div>
				</div>"

		#Send the tree
		render_text info + newTree.to_s
		return
	end

#all functions from here on out are private functions, for use within the actions/sites
#documentation is sparse mostly due to the fact that I've no motivation to do it but
#I'll also use the excuse that we are on some serious time constraints for this project
	private

	def get_size( tables, preds, leftPreds )
		firstPred = nil
		secondPred = nil
		
		if tables.length == 1
			return 1
		end
		
		if tables.length == 2
	
			tableOnePreds = []
			col = COLUMNS.find(:all, :conditions => ["TABLE_NAME = '" + tables[0].grabTable.element + "'"])
			for z in col
				tableOnePreds << z.COLUMN_NAME
			end
			tableTwoPreds = []
			col = COLUMNS.find(:all, :conditions => ["TABLE_NAME = '" + tables[1].grabTable.element + "'"])
			for z in col
				tableTwoPreds << z.COLUMN_NAME
			end	
	
			for x in preds
				if tableOnePreds.include?(x.split("=")[0]) and tableTwoPreds.include?(x.split("=")[1])
					firstPred = x.split("=")[0]
					secondPred = x.split("=")[1]
					break
				end
	
				if tableTwoPreds.include?(x.split("=")[0]) and	tableOnePreds.include?(x.split("=")[1])
					firstPred = x.split("=")[1]
					secondPred = x.split("=")[0]
					break
				end
			end
	
			if firstPred and secondPred
				return calculateSize( tables[0], tableOnePreds ) * calculateSize( tables[1], tableTwoPreds ) + calculateSize( tables[0], tableOnePreds )
			end
	
			return calculateSize( tables[0], tableOnePreds ) * calculateSize( tables[1], tableTwoPreds ) + calculateSize( tables[0], tableOnePreds ) + 99999
			
		else
			### recursive call ###
			
			col = COLUMNS.find(:all, :conditions => ["TABLE_NAME = '" + tables[1].grabTable.element + "'"])
			for z in col
				leftPreds << z.COLUMN_NAME
			end
			rightPreds = []
			col = COLUMNS.find(:all, :conditions => ["TABLE_NAME = '" + tables[0].grabTable.element + "'"])
			for z in col
				rightPreds << z.COLUMN_NAME
			end

			for x in preds
				if leftPreds.include?(x.split("=")[0]) and rightPreds.include?(x.split("=")[1])
					firstPred = x.split("=")[0]
					secondPred = x.split("=")[1]
					break
				end

				if rightPreds.include?(x.split("=")[0]) and	leftPreds.include?(x.split("=")[1])
					firstPred = x.split("=")[1]
					secondPred = x.split("=")[0]
					break
				end
			end
			
			temp_table = Array.new(tables)
			first_table = tables.delete(temp_table[0])
			
			size = get_size( tables, preds, leftPreds.concat(rightPreds) )
			if firstPred and secondPred
				return calculateSize( first_table, rightPreds ) * size + size
			end

			return calculateSize( first_table, rightPreds ) * size + size
		end
	end
	
	def calculateSize( exp, preds )
		if exp.type.eql?("TABLE")
			avg_row_length = TABLES.find(:all, :conditions => ["TABLE_NAME = '" + exp.element + "'"])[0].AVG_ROW_LENGTH
			num_rows = TABLES.find(:all, :conditions => ["TABLE_NAME = '" + exp.element + "'"])[0].TABLE_ROWS
			return avg_row_length * num_rows
		elsif exp.type.eql?("SELECT")
			if preds.include?(exp.element.split("=")[0]) or preds.include?(exp.element.split("=")[1])
				#create indexes
				indexes = []
				col = STATISTICS.find(:all, :conditions => ["TABLE_NAME = '" + exp.grabTable.element + "'"])
				for x in col
					indexes << x.COLUMN_NAME
				end
				
				if indexes.include?(exp.element.split("=")[0]) or indexes.include?(exp.element.split("=")[1])
					#calculate index size
					avg_row_length = TABLES.find(:all, :conditions => ["TABLE_NAME = '" + exp.grabTable.element + "'"])[0].AVG_ROW_LENGTH
					num_rows = TABLES.find(:all, :conditions => ["TABLE_NAME = '" + exp.grabTable.element + "'"])[0].TABLE_ROWS
					card = STATISTICS.find(:all, :conditions => ["TABLE_NAME = '" + exp.grabTable.element + "' AND COLUMN_NAME = '" + exp.element.split("=")[0] + "'"])[0].CARDINALITY
					return avg_row_length * num_rows / card
				else
					avg_row_length = TABLES.find(:all, :conditions => ["TABLE_NAME = '" + exp.grabTable.element + "'"])[0].AVG_ROW_LENGTH
					num_rows = TABLES.find(:all, :conditions => ["TABLE_NAME = '" + exp.grabTable.element + "'"])[0].TABLE_ROWS
					return avg_row_length * num_rows
				end
			else
				avg_row_length = TABLES.find(:all, :conditions => ["TABLE_NAME = '" + exp.grabTable.element + "'"])[0].AVG_ROW_LENGTH
				num_rows = TABLES.find(:all, :conditions => ["TABLE_NAME = '" + exp.grabTable.element + "'"])[0].TABLE_ROWS
				return avg_row_length * num_rows
			end
		end
	end

	def generate_joins( tables )
		result = []
				
		if tables.length == 1
			return [tables]
		end
		
		for x in tables
			temp = Array.new(tables)
			temp.delete(x)
			
			nested_result = generate_joins( temp )
			for y in nested_result
				temp2 = []
				temp2 << x
				for z in y
					temp2 << z
				end
				result << temp2
			end
		end

		return result
	end

	def createTree( parsed_statement )
		load "BinaryTree.rb"
		
		s = ""
		first = true
		for x in parsed_statement[:projections]
			if first
				s += x
				first = false
			else
				s += ", " + x
			end
		end
		tree = BinaryTree.new(s,"PROJECT")
		
		s = ""
		first = true
		for x in parsed_statement[:select_preds]
			if first
				s += x
				first = false
			else
				s += " AND " + x
			end
		end
		for x in parsed_statement[:join_preds]
			if first
				s += x
				first = false
			else
				s += " AND " + x
			end
		end
		
		tree.root.left= BinaryNode.new(s, "SELECT")
		
		s = ""
		size = parsed_statement[:tables].length - 1
		current = nil;
		parent = nil;
		first = nil;
		for x in (0..size)
			val = parsed_statement[:tables][x]

			if x == size
				val = parsed_statement[:tables][x]

				if current
					parent.left= BinaryNode.new(val,"TABLE")
				else
					first = current = BinaryNode.new(val,"TABLE")
				end
			else
				if current
					current.right= BinaryNode.new(val,"TABLE")
					current.left= BinaryNode.new("","CROSS")
					parent = current
					current = current.left
				else
					first = current = BinaryNode.new("","CROSS")
					current.right= BinaryNode.new(val,"TABLE")
					current.left= BinaryNode.new("", "CROSS")
					parent = current
					current = current.left
				end
			end
		end
		tree.root.left.left= first
		
		return tree
	end	

	def createTreePushed( parsed_statement )
		load "BinaryTree.rb"

		s = ""
		first = true
		for x in parsed_statement[:projections]
			if first
				s += x
				first = false
			else
				s += ", " + x
			end
		end
		tree = BinaryTree.new(s,"PROJECT")

		s = ""
		first = true
		for x in parsed_statement[:join_preds]
			if first
				s += x
				first = false
			else
				s += " AND " + x
			end
		end

		tree.root.left= BinaryNode.new(s, "SELECT")

		s = ""
		size = parsed_statement[:tables].length - 1
		current = nil;
		parent = nil;
		first = nil;
		for x in (0..size)
			val = parsed_statement[:tables][x]

			if x == size
				if current
					parent.left= val
				else
					first = current = val
				end
			else
				if current
					current.right= val
					current.left= BinaryNode.new("","CROSS")
					parent = current
					current = current.left
				else
					first = current = BinaryNode.new("","CROSS")
					current.right= val
					current.left= BinaryNode.new("", "CROSS")
					parent = current
					current = current.left
				end
			end
		end
		tree.root.left.left= first

		return tree
	end	

	def createJoins( tables, joins, selects, pos )
		if pos == (tables.length - 1)
			tablesPreds = []
			col = COLUMNS.find(:all, :conditions => ["TABLE_NAME = '" + tables[pos] + "'"])
			for z in col
				tablesPreds << z.COLUMN_NAME
			end
			predicateToInclude = ""
			for x in selects
				if tablesPreds.include?(x.split("=")[0])
					predicateToInclude = x
				end
			end

			return "SCAN (" + predicateToInclude + ") (" + tables[pos] + ")"
		end

		table_one_preds = []
		(0..pos).each do |x|
			col = COLUMNS.find(:all, :conditions => ["TABLE_NAME = '" + tables[x] + "'"])
			for z in col
				table_one_preds << z.COLUMN_NAME
			end
		end
		table_two_preds = []
		col = COLUMNS.find(:all, :conditions => ["TABLE_NAME = '" + tables[pos+1] + "'"])
		for z in col
			table_two_preds << z.COLUMN_NAME
		end
		joinPredicateToInclude = ""
		first = true
		for x in joins
			if (table_one_preds.include?(x.split("=")[0]) and table_two_preds.include?(x.split("=")[1])) or
				 (table_one_preds.include?(x.split("=")[1]) and table_two_preds.include?(x.split("=")[0]))
				if first
					joinPredicateToInclude += x
					first = false
				else
					joinPredicateToInclude += " AND " + x
				end
			end
		end


		tablesPreds = []
		col = COLUMNS.find(:all, :conditions => ["TABLE_NAME = '" + tables[pos] + "'"])
		for z in col
			tablesPreds << z.COLUMN_NAME
		end
		selPredicateToInclude = ""
		for x in selects
			if tablesPreds.include?(x.split("=")[0])
				selPredicateToInclude = x
			end
		end
	
		return "JOIN (" + joinPredicateToInclude +
						 ") (SCAN (" + selPredicateToInclude +
							 ") (" + tables[pos] + 
						 ")) (" + createJoins( tables, joins, selects, pos + 1 ) + 
					 ")"
	end
  
	def parse(sql_statement)
		@words = sql_statement.split(' ')
		mode = -1
		projections	 = []
		select_pred	 = []
		join_pred  	 = []
		tables     	 = []
		current_pred = ""
		@words.size().times do |x|
			#for each of the words in the loop, check shit
			if @words[x].downcase.eql?("select")
				mode = 1
			elsif @words[x].downcase.eql?("from")
				mode = 2
			elsif @words[x].downcase.eql?("where")
				mode = 3
			elsif @words[x].downcase.eql?("and")
				list_of_objects = []
				tables.length.times do |y|
					col = COLUMNS.find(:all, :conditions => ["TABLE_NAME = '" + tables[y] + "'"])
					for z in col
						list_of_objects << z.COLUMN_NAME
					end
				end
				# if is join pred, add to joins, else add to selects
				# join preds are preds with the right side of the equation
				# an object in the table
				pred = current_pred.split("=")
				if pred and pred[1] and list_of_objects.include?(pred[1])
					join_pred << current_pred
				elsif pred and pred[1]
					select_pred << current_pred
				end
				current_pred = ""
				mode = 3
			elsif mode == 1
				for z in @words[x].split(",")
						projections << z
				end
			elsif mode == 2
				for z in @words[x].split(",")
						tables << z
				end
			elsif mode == 3
				current_pred << @words[x]
			else
				return "error"
			end
		end
	
		# if is join pred, add to joins, else add to selects
		# join preds are preds with the right side of the equation
		# an object in the table
		list_of_objects = []
		tables.length.times do |y|
			col = COLUMNS.find(:all, :conditions => ["TABLE_NAME = '" + tables[y] + "'"])
			for z in col
				list_of_objects << z.COLUMN_NAME
			end
		end
		pred = current_pred.split("=")
		if pred and pred[1] and list_of_objects.include?(pred[1])
			join_pred << current_pred
		elsif pred and pred[1]
			select_pred << current_pred
		end
	
		#old version
		#render_text "(SELECT (" + projections + ") (" + select_pred + ") (" + join_pred + ") (" + tables + "))"
	
		parsed_statement = { :projections => projections, :select_preds => select_pred, :join_preds => join_pred, :tables => tables }
		return parsed_statement
	end

	def generate_form(num, tabs, tabs_t, tabs_c, result, action, div, step, query)
		form = "<div class='tab_content'>
					<ul class='step_tabs'>"
		for x in (0..tabs.length-1)
			form += "<li title='" + tabs[x] + "_" + num + "' onclick='tabs(this);'>" + tabs_t[x] + "</li> "
		end
	
		form += "</ul>"
		
		for x in (0..tabs.length-1)
			form += "<div id='" + tabs[x] + "_" + num + "'>" + tabs_c[x] + "</div>"
		end
		
		form += "</div>" + result + "<form action='/r/main/" + action + "' method='post' 
						onsubmit=\"new Ajax.Updater('" + div + "', '/r/main/" + action + "', 
						{asynchronous:true, evalScripts:true, onComplete:function(request){new Effect.BlindDown(&quot;" + step +
						"&quot;,{duration:0.5});new Effect.Highlight(&quot;" + step + "&quot;,{});loading();},
						onLoading:function(request){loading();}, 
						parameters:Form.serialize(this)}); return false;\">
					<input name='commit' type='submit' value='Next step' onclick='restart(this);' />
					<input name='query' type='hidden' value=' " + query.to_s.gsub(/\'/, '"') + " ' />
				</form>"
				################################ Placed to get inType to shut up '
		return form
	end
end
